/**
 * 项目名称: 堆排序.cpp
 * 项目路径: study/DataStructure/数据结构/排序/选择排序
 * 编辑时间: 2024年08月27日16时58分41秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

/**
 * 以k为根的子树调整为大根堆
 * @param A
 * @param k
 * @param len
 */
void HeadAdjust(int A[],int k,int len){
    A[0]=A[k];//A[0]暂存子树的根节点
    for(int i = 2* k;i<=len;i*=2){//沿key较大的子节点向下筛选
        if(i<len && A[i]<A[i+1])
            i++;//取key较大的子结点的下标
        if(A[0]>=A[i])break;//筛选结束
        else{
            A[k]=A[i];//将A[i]调整到双亲结点上
            k=i;//修改k的值,以便继续向下筛选
        }
    }
    A[k]=A[0];//被筛选结点的值放入最终位置
}
/**
 * 建立大根堆
 * @param A
 * @param len
 */
void BuildMaxHeap(int A[],int len){
    for(int i = len/2;i>0;i--)//从后往前调整所有非终端结点
        HeadAdjust(A,i,len);
}

/**
 * 堆排序
 * @param A
 * @param len
 */
void HeapSort(int A[],int len){
    BuildMaxHeap(A,len);//初始建堆
    for(int i =len;i>1;i--){//n-1趟的交换和建堆过程
        swap(A[i],A[1]);//堆顶元素和堆底元素交换
        HeadAdjust(A,1,i-1);//把剩余的待排序元素整理成堆
    }
}